Aggregate Method

Computer Science

Use the Aggregate Method, the Banker's Method, or the Physicist's Method to perform Amortized Analysis.

Dynamic array: n calls to PushBack.

• Let c_i = cost of i'th insertion.
• c_i = 1 + { i - 1 if i - 1 is a power of 2 OR 0 otherwise
• (Ε ⁿ_i=1c_i)/n
• (n + Ε^{⌊log₂(n-1)⌋}_j=12^j)/n
• (O (n)) / n
• O(1)
• Worst case cost is O(n). Amortized cost is O(1).

(ALGS201x)